package org.shj.algorithm.tuihuo;

import java.util.LinkedList;
import java.util.List;
import java.util.Random;

//旅行商问题的 模拟退火算法
public class MoniTuiHuo {
	
	public int cityCount = 9;
	
	public int calTimes = 200; 
	
	public double T = cityCount * 100.0;//初始温度
	public double Tmin = 0.001; //终止温度
	public double rate = 0.99;  //降温速度
	
	public double rate1 = 0.001; //接受比较差的路径的概率， 在一定程度上可以跳出局部最优解
	
	//各个城市间的距离
	public static int[][] d = new int[][]{
			{0, 1, 2, 3, 4, 5, 6, 7, 8},
			{1, 0, 2, 4, 7, 8, 6, 9, 3},
			{2, 2, 0, 3, 6, 9, 8, 5, 4},
			{3, 4, 3, 0, 9, 2, 1, 6, 8},
			{4, 7, 6, 9, 0, 5, 2, 9, 6},
			{5, 8, 9, 2, 5, 0, 4, 7, 9},
			{6, 6, 8, 1, 2, 4, 0, 3, 5},
			{7, 9, 5, 6, 9, 7, 3, 0, 7},
			{8, 3, 4, 8, 6, 9, 5, 7, 0}
		};
	
	public int[] genSingle(){
		int[] single = new int[cityCount];
		List<Integer> sin = new LinkedList<Integer>();
		for(int i = 1 ; i <= cityCount ; i++){//1~9 代表第1～9个城市
			sin.add(i);
		}
		Random r = new Random();
		for(int i = 0; i < cityCount - 1; i++){
			int ind = r.nextInt(sin.size());
			single[i] = sin.get(ind);
			sin.remove(ind);
		}
		single[cityCount - 1] = sin.get(0);
		return single;
	}

	public static void main(String[] args){
		MoniTuiHuo mnth = new MoniTuiHuo();
		
		mnth.start();
	}
	
	public void start(){
		Random r = new Random();
				
		int[] path = genSingle();
		int[] newPath = null;
		int count = 0;
		int repeat = 1;
		
		while( T > Tmin){
			count++;
			for(int i = 0 ; i < repeat; i++){
				newPath = genNewPath(path);
				
				int disOld = calDis(path);
				int disNew = calDis(newPath);
				
				if(disNew < disOld){
					path = newPath;
				}else{
					if( Math.exp((disNew - disOld) / T) > r.nextDouble()){
						path = newPath;
					}
				}
			}
			
			repeat++;
			T = T * rate;
		}
		System.out.println("Count: " + count);
		System.out.print("distance = " + calDis(path) + ": ");
	}
	
	public int[] genNewPath(int[] path){
		int[] newPath = new int[path.length];
		for(int i = 0 ; i < path.length; i++){
			newPath[i] = path[i];
		}
		
		Random r = new Random();
		
		int f1 =  r.nextInt(path.length);
		int f2 = r.nextInt(path.length); ;
		while(f1 == f2){
			f2 = r.nextInt(path.length);
		}
		
		newPath[f1] = path[f2];
		newPath[f2] = path[f1];
		
		return newPath;
	} 
	
	private static int calDis(int[] single){
		int distance = 0;
		for(int i = 0 ; i < single.length - 1; i++){
			distance += d[single[i] - 1][single[i + 1] - 1];
		}
		distance += d[single[single.length - 1] - 1][single[0] - 1]; //从最后一个城市到出发城市的距离
		return distance;
	}
}
